# 给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。
# 即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。
#
# 回文 是正着读和反着读一样的字符串。
#
# 子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。
#
# 例如，"ace" 是 "abcde" 的一个子序列。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/unique-length-3-palindromic-subsequences
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        """
        对26个字母，找每个字母在s中出现的第一个和最后一个位置
        如果中间字符有重复的，也会被最外围的字符构成的回文所包含
        然后枚举中间的字符种类，就是这个字母构造的长度为3的回文子序列的贡献
        :param s:
        :return:
        """
        ans, n = 0, len(s)
        for i in range(26):
            left, right = 0, n - 1
            # 第一次出现的位置
            while left < n and ord(s[left]) - ord('a') != i:
                left += 1
            while right >= 0 and ord(s[right]) - ord('a') != i:
                right -= 1
            if right - left < 2:  # a b a 最少应该相差2
                continue
            charset = set()  # 用集合统计中间字符种类
            for k in range(left + 1, right):
                charset.add(s[k])
            ans += len(charset)
        return ans


if __name__ == '__main__':
    sol = Solution()
    print(sol.countPalindromicSubsequence("aabca"))
